刷到快吐了 來看點系統面試課程

系統面試

面試策略

1. start by clarifying requirements
   • ask lots of questions
   • think out loud (let interviewer see yout thought)
   • break down problem, focus on important question
   • suppose some data (user amount, qps, machine amount...etc)
     • focus on horizontal partitioning?
     • focus on transaction rate?
     • focus on bigdata storage?
     • focus on data consistency?
     • how fast is fast enough?
     • how much downtime can you tolerate?
     • ...etc
   • working backwards (start from the customer experience to define the requirements)
     • identidy who are the customers
     • whar are their use cases
     • which use cases do I need to concern myself with
2. Sketching out the design
   • start with heigh-level components
   • Then flesh out each component as time permits
     • how do they scale
     • how are they distributed for availabiltiy
   • let the interviewer talk
   • identify bottlenecks, maintenance, costs concerns as you go
     • show that you understand tradeoffs of the choises you are making
3. Be Honest
   • don't pretend to know stuff you don't know.
   • if you're steered into a direction you're unfamiliar with, say so.
   • don't give up, try to resolve it.
4. Defending your design
   • the interviewer will try to poke holes in your design.
   • what happens if X fails?
   • What happens if we get a sudden surge of traffix / data?
   • Did you meet the scaling & availabiliy requirements you definded?
   • does your system meet all of the use cases?
   • how would you make it better?
   • how would you optimize or simplify it?
   • what is its operatinal burden? how will you monitor it?

經典案例

how to design a URL shortening service?

clarifying requirements

1. what sort of scale are we talking about?
2. any restrictions on the characters we use?
3. how short is short?
4. how about vanity url?
5. do we let them edit and delete urls?
6. how long will you record these url?

design it

(Design user requirement first)
Add new URL
long URL, user ID(optional) -> status, short URL
- what if someone else shortened it earlier?
url -> e.g. base36 encoding (0-25 by a-z 26-36 by 0-9)

Add new vanity URL
long URL, user ID, vanity URL -> status

Update URL
long URL, user ID, updated long URL -> status, existing short URL

Delete URL
long URL, userID -> status

Display mapping
long URL, userID -> status, short URL

Redirect
short URL -> redirect to long URL

(Desion Component)
User device -> Load Balancer (Geo-routing) -> ECS -> cache -> NoSql

(Describe user flow)
GET /abc111
return status 301 with redirect url
(301 is always redirect, 302 is temp redirect)
(discuss with intervier which one is required)

繼續隨意刷刷

Jump Game II

Q: https://leetcode.com/problems/jump-game-ii/

   class Solution {
    public int jump(int[] nums) {
        int[] min = new int[nums.length];
        int nowMax = nums[0];
        int preStep = 0;
        int nextMax = 0;
        int nextStep = 0;
        min[0] = 0;
        for (int i = 1;i < nums.length;i++) {
            if (preStep + nowMax < i) {
                preStep = nextStep;
                nowMax = nextMax;
                nextMax = 0;
            }
            min[i] = min[preStep] + 1;
            if (nums[i] + i >= nextStep + nextMax) {
                nextMax = nums[i];
                nextStep = i;
            }
        }
        return min[min.length - 1];
    }
}

Rotate Image

Q: https://leetcode.com/problems/rotate-image/description/

    class Solution {
    public void rotate(int[][] matrix) {
        for(int i = 0; i < matrix.length/2; i++){
            for(int j = i; j < matrix.length - 1 - i; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[matrix.length - 1 - j][i];
                matrix[matrix.length - 1 - j][i] = matrix[matrix.length - 1 - i][matrix.length - 1 - j];
                matrix[matrix.length - 1 - i][matrix.length - 1 - j] = matrix[j][matrix.length - 1 - i];
                matrix[j][matrix.length - 1 - i] = temp;
            }    
        }
    }
}

Group Anagrams

Q: https://leetcode.com/problems/group-anagrams/description/

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        final Map<String, List<String>> m = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            if (m.containsKey(key)) {
                m.get(key).add(str);
            } else {
                final List<String> l = new ArrayList<>();
                l.add(str);
                m.put(key, l);
            }
        }
        final List<List<String>> result = new ArrayList<>();
        for (Map.Entry<String, List<String>> entry : m.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }
}

後來發現可以更加優化
直接把字串都轉為類似hash的字串
時間可以縮為O(MN)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) count[c - 'a']++;

            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

Minimum Window Substring

Q: https://leetcode.com/problems/minimum-window-substring/description/

class Solution {
    public String minWindow(String s, String t) {

        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
        Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }
        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
        int[] ans = { -1, 0, 0 };

        while (r < s.length()) {
            char c = s.charAt(r);
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }
            while (l <= r && formed == required) {
                c = s.charAt(l);
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
                l++;
            }
            r++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

Split Linked List in Parts

Q: https://leetcode.com/problems/split-linked-list-in-parts/description/?envType=daily-question&envId=2023-09-06

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] result = new ListNode[k];
        int count = 0;
        ListNode now = head;
        while(now != null) {
            count++;
            now = now.next;
        }
        int mod = count % k;
        int size = count / k;
        now = head;
        for (int i = 0;i < k;i++) {
            if (now != null) {
                ListNode tail = new ListNode();
                tail.next = now;
                result[i] = now;
                for (int j = 0;j < size;j++) {
                    now = now.next;
                    tail = tail.next;
                }
                if (mod > 0) {
                    now = now.next;
                    tail = tail.next;
                    mod--;
                }
                tail.next = null;
            }
        }
        return result;
    }
}

今天有個google interview workshop
來記下幾個重點

• 多討論
• 不要怕問提示
• 討論想法前先定義好問題 提出所有edge case的可能
• 寫之前先與面試官討論想法
• 若想不出來答案 可以先想一個小的問題 然後慢慢拓展成大問題（但要解釋清楚 自己的假設是什麼）
• 能夠分析解法的好壞

資料結構
Vector / List / Array
String
Heap
Linked List
Queue
Stack
HashMap
HashSet
Tree
Trie

演算法操作
insert
delete
move
query
traverse
sort
DP
Greedy
Multi thread

Googler 各資料結構/算法關注重點:

Vector / List / Array

優點:
random access O(1)
缺點:
require sequential memory
hard to split
hard to resize
out of index issue
需知:
good for quick sort
not good for merge sort
why it needs sequential memory
push_back/append complexity (O(1)? O(N)>)
Compare to Array

Linked List

優點:
easy to delete a node
easy to insert a node
easy to concat
easy to divide
缺點:
can't do random access
spend time to delete
需知:
good for merge sort (why?)
bad for quick sort (why?)
circular detection
difference between singly and doubly
queue/stack can be implenmented by Linked-List

Queue & Stack

優點:
Queue
FIFO
Enque & Deque
Stack
LIFO
Push & Pop
缺點:
can't do random access
hard to delete random element
需知:
how to implement then
by linked list
by array
by others?
how to use them to solve BFS/DFS
BFS -> Queue
DFS -> Stack

HashMap

優點:
O(1) to put/get the value with key
Key-Value pair
No duplicate keys
缺點:
Can't do random access
Hard to concat/apart
No order
No duplicate keys
需知:
Whar hash is
Why O(1) for "get" function
Exception case?
Hash colision
Useful to reduce the Time Complexity
Good for pre-processing
Tradeoff between space and time
Can have duplicate values
What happens if hashing is not O(1)?
Map? HashMap?
OrderedMap

HashSet

優點:
O(1) to add/get/delete the value
O(1) to know if the value is in
No duplication
缺點:
Can't do random access
No order
No duplictation
需知:
Reason of O(1)
v.s. HashMap
HashSet? Set?

Tree

優點:
O(logN) access time
easy to append
can be used to search
pre-processing
缺點:
hard to delete
unbalanced issue
hard to copy
hard to change the order
hard to do in-place sorting
需知:
pre-order, ino-order, post-order
知道以下不同
Tree
Binary Tree
Binary Search Tree
Balanced / Unbalanced Tree
Full Tree
Complete Tree
How to balance a Tree
Issues of an Unbalanced Tree
Red-Black Tree

Priotity Queue

優點:
O(1) to find out the min/max
缺點:
O(LogN) for enque and deque
Can't do random access
hard to delete the element

tips: 量不大時可以考慮用bucket sorting

Tree and Graph Traversal

BFS:
DFS:

Others:
DP
Multi-Threading
mutex Lock
sempahore lock
read lock
write lock

System Design interview

BAS CASE

Q: please design Time query Service
(drawing 30min..)
A: OK, here's my solution
 

GOOD CASE

 Q: please design Time query Service
 A: Hmm.. atime service, I'm imaging it'a service that allow users to query and get the current time, is it correct? how many user do we expect?
 Q: Yes, a service to allow user to get current time, Let's start from a limited users like 10,000.
 A: 10,000 users, Let's assume 1 user might call to service 10times, may I need to consider auth system?
 Q: ...
 A: ...